//此题的时间复杂度为O(mlogn)，堆的存在使得不用遍历一遍全部的点找到最短的那一条，但是也使得每次优化和修改最短路，都需要logn的时间
//由于此算法还是dijkstra算法，所以还是必须是全部正权边，但是这个时间复杂度更适合用来处理稀疏图
#include <iostream>
#include <cstring>
using namespace std;

const int N = 200010;
const int INF = 0x3f3f3f3f;
int h[N], e[N], ne[N], w[N], idx = 0; //带权值的邻接表，w用来存储权值，w[k]表示k代指的那条边的长度
int dist[N];                          //一样是用来存储现阶段最短路径
bool st[N];                           //同样判断是否已经确定了完美最短路径
int heap[N], ph[N], hp[N], Size = 0;  //模拟堆
int n, m, x, y, z;

void h_swap(int a, int b) //模拟堆的两个结点交换
{
    swap(ph[hp[a]], ph[hp[b]]); //先由堆中存储边长的结点的编号索引到的图中对应的要到达的点的编号，再由找到的编号找到反向索引数组，防止交换以后找不到
    swap(hp[a], hp[b]);         //再交换堆中存储边长的结点索引邻接表编号的数组
    swap(heap[a], heap[b]);     //最后交换邻接表中存储的值
    return;
}

void up(int u) //将堆中的某个结点尽可能的往上移动
{
    while (u / 2 && heap[u / 2] > heap[u]) //由于创建的是小根堆，所以如果我比我上面的大，那就和上面的交换
    {
        h_swap(u / 2, u);
        u >>= 1;
    }
    return;
}

void down(int u) //将堆中的某个结点尽可能的往下移
{
    int t = u;
    if (2 * u <= Size && heap[2 * u] < heap[t])
        t = 2 * u;
    if (2 * u + 1 <= Size && heap[2 * u + 1] < heap[t])
        t = 2 * u + 1;
    if (t != u)
    {
        h_swap(t, u);
        down(t);
    }
    return;
}

void h_add(int k, int x) //将到结点k的距离为x这一信息入堆
{
    Size++;
    heap[Size] = x;
    hp[Size] = k;
    ph[k] = Size;
    up(Size);
    return;
}

void del(int k) //将点k从堆中删除
{
    k = ph[k];
    h_swap(k, Size);
    Size--;
    up(k);
    down(k);
    return;
}

void add(int x, int y, int z) //将x到y距离为z这一信息加入邻接表
{
    e[idx] = y;
    w[idx] = z;
    ne[idx] = h[x];
    h[x] = idx++;
    return;
}

void alter(int k, int x)
{
    heap[ph[k]] = x;
    up(ph[k]);
    down(ph[k]);
    return;
}

int dijkstra()
{
    dist[1] = 0;
    h_add(1, dist[1]);
    while (Size) //只要堆中还有元素，既还存在可以确定还是还没确定最短路径的点
    {
        int t = hp[1];                         //找到现阶段距离1最短的点,既堆顶
        del(hp[1]);                            //将堆顶删除
        st[t] = true;                          //将其确认为最短路径
        for (int i = h[t]; i != -1; i = ne[i]) //遍历所有本点可达的点，尝试更新他们
        {
            int j = e[i];
            if (!st[j] && (dist[j] > dist[t] + w[i])) //如果找到了更短的距离
            {
                dist[j] = dist[t] + w[i]; //那么就更新他
                if (!ph[j])               //如果j没入过堆，则入堆
                    h_add(j, dist[j]);
                else //不然就在堆里面修改它
                    alter(j, dist[j]);
            }
        }
    }
    return dist[n];
}

int main()
{
    memset(h, -1, sizeof heap);      //一开始的指针指向全部为空，代表点与点之间没有关联
    memset(dist, 0x3f, sizeof dist); //现阶段所有点到1的距离都默认为最大值
    memset(st, false, sizeof st);    //现阶段所有的最短路径全部还没有确认
    cin >> n >> m;
    while (m--)
    {
        cin >> x >> y >> z;
        add(x, y, z);
    }
    int t = dijkstra();
    if (t == INF)
        cout << -1;
    else
        cout << t;
    return 0;
}